// 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

var permute = function(nums) {
    nums.sort((a, b) => { return a - b });
    let arr = [];
    let used = {};
    let use = {};

    function change(path) {
        if (path.length == nums.length) {
            if (use[path]) { return }
            arr.push(path.slice());
            use[path] = true;
            return;
        }
        for (let i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            path.push(nums[i]);
            used[i] = true; //哈希去重
            change(path);
            path.pop();
            used[i] = false;
        }
    }
    change([]);
    console.log(arr);
    return arr;
}


let a = [1, 1, 2]
permute(a)


// 树层去重，先排序，两个树层重复就舍去
// 树层上去重(used[i - 1] == false)
var permuteUnique = function(nums) {
    nums.sort((a, b) => {
        return a - b
    })
    let result = []
    let path = []

    function backtracing(used) {
        if (path.length === nums.length) {
            result.push(path.slice())
            return
        }
        for (let i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) {
                continue
            }
            if (!used[i]) {
                used[i] = true
                path.push(nums[i])
                backtracing(used)
                path.pop()
                used[i] = false
            }


        }
    }
    backtracing([])
    return result
};